Maximum-Cup 2018 D - Many Go Round

https://atcoder.jp/contests/maximum-cup-2018/tasks/maximum_cup_2018_d

解説

code: python

n, m, l, x = map(int, input().split())

a = list(map(int, input().split()))

# dpij := 燃料を i 番目までみて休憩所 j に止まるのに必要な最小の周回回数

# 遷移のときに、dpi を作るのに必要なのは dpi-1 の情報だけなので、添字 i の部分のサイズは2にすることができる

# 3で剰余をとる

dp = [99999 * m for _ in range(3)]

for i in range(3):

# 動かなくていいので周回回数は0

dpi0 = 0

# print(dp)

# 0, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999], 0, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, [0, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999

for i in range(n):

for j in range(m):

# 燃料 i 番目を使うと距離 i 進む

# 1 周回ると位置はまた戻ってくるので、m で剰余をとると、燃料 i 番目を使ったときにいる位置は (j+ai) % m

# 周回回数については、dpij + ai / m で計算できる

# 休憩所 j での最小周回回数に進む距離を一周の距離で割った数を足すことで、小数点単位で周回回数を計算できる

dp(i + 1) % 3[(j + ai) % m] = min(dp(i + 1) % 3[(j + ai) % m], dpi % 3j + ai / m)

dp(i + 1) % 3j = min(dp(i + 1) % 3j, dpi % 3j)

# print(dp)

# 0, 0.09090909090909091, 99999, 99999, 0.36363636363636365, 0.45454545454545453, 0.5454545454545454, 99999, 99999, 0.8181818181818181, 0.9090909090909092], 0, 0.09090909090909091, 1.1818181818181819, 1.2727272727272727, 0.36363636363636365, 0.45454545454545453, 0.5454545454545454, 1.6363636363636365, 0.7272727272727273, 0.8181818181818181, 0.9090909090909092, [0, 0.09090909090909091, 1.1818181818181819, 1.2727272727272727, 0.36363636363636365, 0.45454545454545453, 0.5454545454545454, 1.6363636363636362, 0.7272727272727273, 0.8181818181818181, 0.9090909090909092

print('Yes' if dpn % 3l <= x else 'No')

code: python

n, m, l, x = map(int, input().split())

a = list(map(int, input().split()))

# dpij := i-1 番目のタンクまでで番号 j の休憩所にいるための最小周回数

dp = [10 ** 10 * m for _ in range(n + 1)]

dp00 = 1

for i in range(n):

for j in range(m):

dpi + 1[(j + ai) % m] = min(dpi[(j + ai) % m], dpij + (j + ai) // m)

if dpnl <= x:

print("Yes")

else:

print("No")

テーマ

#dp

蟻本 2-3 個数制限付き部分和問題

メモ

Maximum-Cup 2018 D Many Go Round 解説

Maximum-Cup 2018 D Many Go Round

提出

code: python

n, m, l, x = map(int, input().split())

a = list(map(int, input().split()))

xx = x

candidate = l

while xx > 1:

candidate.append(candidate-1 + m)

xx -= 1

# print(a)

# 1, 4, 5, 8, 9

# print(candidate)

# 7, 18, 29, 40, 51

# O(pow(2, 10000))

# dpi := i に到達できるか

dp = False * (candidate-1 + 1)

for v in a:

dpv = True

for i in range(candidate-1 + 1):

# vを何回でも使ってしまう

for v in a:

if dpi and i + v < candidate-1 + 1:

dpi + v = True

# print(dp)